class Solution {
public:
    bool is(int x,int y,int k){
        int ret = 0;
        while(x > 0 || y > 0){
           if(x > 0){
               ret += x % 10;
               x /= 10;
           }
           if(y > 0){
               ret += y % 10;
               y /= 10;
           }
        }
        return ret <= k;
    }
    int movingCount(int m, int n, int k) {
        vector<vector<int> > dp(m + 2,vector<int>(n + 2,0));
        dp[1][1] = 1;
        int ret = 1;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0 && j == 0) continue;
                if(is(i,j,k)){
                   
                    if(dp[i][j+1] || dp[i+1][j] || dp[i+2][j+1] || dp[i+1][j+2] ){
                        dp[i+1][j+1] = 1;
                        ret++;
                    }
                }
            }
        }
        return ret;
    }
};
